package DP1;

/**
 * 剑指 Offer 47. 礼物的最大价值
 * 在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。
 * 你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、
 * 直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
 */
public class Main1 {

    public static void main(String[] args) {
        int[][] arr = {{1,3,1},{1,5,1},{4,2,1}};
        System.out.println(maxValue(arr));
    }

    public static int maxValue(int[][] grid){
        int row = grid.length;  // 行
        int col = grid[0].length;  // 列
        int[][] DP = new int[row+1][col+1]; // 创建一个[row+1][col+1]的数组


        for (int i = 1; i <= row; i++) {
            for (int j = 1; j <= col; j++) {
                DP[i][j] = Math.max(grid[i-1][j-1]+DP[i][j-1],grid[i-1][j-1]+DP[i-1][j]);
            }
        }

        return DP[row][col];
    }

}
